#include <iostream>
#include <unordered_map>

#include "common/utils.hpp"

/*
1.前序遍历特性：根节点总是在前序遍历序列的第一个位置
2.中序遍历特性：根节点将中序遍历序列分为左右子树。左子树的中序遍历序列在根节点左侧，右子树的则在右侧
3.递归构建：
    - 从前序遍历中取出第一个元素作为当前根节点
    - 在中序遍历中找到根节点的索引，以此划分左右子树的节点序列
    - 递归构建左右子树
*/
TreeNode* traversal(std::vector<int>& preorder, std::vector<int>& inorder, int preorderL, int preorderR, int inorderL, int inorderR, std::unordered_map<int, int>& inorderMap) {
    if (preorderL >= preorderR) return nullptr;

    // 前序遍历序列 首个元素是根节点
    int nodeValue = preorder[preorderL];
    TreeNode* node = new TreeNode(nodeValue);

    // 找到这个根节点在中序遍历中的索引，左边序列构成左子树，右边序列构成右子树
    int inorderIndex = inorderMap[nodeValue];
    // 左边节点个数
    int lSize = inorderIndex - inorderL;
    // 左边子树
    int pL = preorderL + 1;
    int pR = pL + lSize;
    int iL = inorderL;
    int iR = iL + lSize;
    node->left = traversal(preorder, inorder, pL, pR, iL, iR, inorderMap);
    // 右边子树
    pL = preorderL + 1 + lSize;
    pR = preorderR;
    iL = inorderIndex + 1;
    iR = inorderR;
    node->right = traversal(preorder, inorder, pL, pR, iL, iR, inorderMap);

    return node;
}

// preorder、inorder中没有重复元素
TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    // inorder 值 -> 索引 map
    std::unordered_map<int, int> inorderValueToIndex;
    for (int i = 0; i < inorder.size(); i++) {
        inorderValueToIndex[inorder[i]] = i;
    }

    return traversal(preorder, inorder, 0, preorder.size(), 0, inorder.size(), inorderValueToIndex);
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> preorder = { 10, 6, 3, 9, 16, 14, 19 };
    std::vector<int> inorder = { 3, 6, 9, 10, 14, 16, 19 };
    TreeNode* ret = buildTree(preorder, inorder);
    printTreeNode(ret);
}